Global-based communications networks such as the Internet have evolved from an early, research-based system with limited access, to a truly world wide network with millions of users. The original network protocol, TCP/IP, was designed on the basis that system users would connect to the network for strictly legitimate purposes. As a consequence, no particular consideration was given to security issues. In recent years, however, the incidence of malicious attacks on the Internet has grown to an alarming proportion. These attacks take on a variety of forms, and often lead to a complete disruption of service for a targeted victim.
One such attack is based on the concept of flooding a victim with so much traffic that the victim's server cannot cope, or with very effective malicious packets at lower rates. Due to its anonymous nature, the Internet Protocol (IP) makes it extremely difficult to precisely identify the real source of any given datagram, and thus any given flow, if the source wishes to remain unknown. This peculiarity is often exploited, during a malicious Denial of Service (DoS) attack, to hide the source of the attack. A DoS attack involves blocking somebody's ability to use a given service on the network. DoS attacks are common across the Internet with many being launched daily at various targets.
Thus, it is very difficult to trace the real source of the attack if an attacker uses a spoofed source address, i.e. replaces its legitimate address with an illegitimate one. It is expected that if attackers were open to identification the incidence of DoS attacks would decrease significantly.
Several methods have been proposed for solving the IP trace back problem. A thorough overview on the topic is given by H. F. Lipson in a special report entitled “Tracking and Tracing Cyber-Attacks: Technical Challenges and Global Policy Issues”, CERT Coordination Center. Among all the other techniques that this paper describes, a hop-by-hop trace back scheme is discussed. This mechanism consists of a manual and tedious process by which a network administrator gathers information on each router on the upstream path of the flow being traced one step at a time until the source is reached.
Other prior art solutions involve systems where routers are requested to insert their IP addresses, or other unique identifiers, into the IP packet headers. The victim of an attack reconstructs the path by using the information gathered by correlating all the received, marked datagrams. This system is described by S. Savage, D. Wetherall, A. Karling and T. Anderson in “Practical Network Support for IP Trace back”, SIGOMM'00, Stockholm, Sweden.
Another back-tracing method is iTrace, which relies on routers sending a new type of Internet control message protocol (ICMP) message to the destination of the datagram examined with a certain probability. By gathering a given number of these messages the receiver of a certain flow can reconstruct the path to the source. This method is described by S. Bellovin, M. Leech, T. Taylor, “ICMP Trace back messages”, IETF work in progress.
Finally, the third classical approach is to rely on routers keeping track of all packets they forward in some efficient matter. In a hash-based solution every router keeps a table containing a hashed value from every packet forwarded during a given interval. If a particular flow is to be traced, routers on the upstream path forward their tables to an entity that will carry out a correlation process to determine the next hop. The method relies on Bloom filters to speed up the look-up process in the table. This method was described by C. Snoeren, C. Patridge, L. Sanchez et al., “Hash-based IP Trace back”, SIGCOMM'01, San Diego.
The Applicant's co-pending U.S. patent application Ser. No. 10,635,602, filed Aug. 7, 2003 for a “Mechanism for Tracing-back Anonymous Network Flows in Autonomous Systems” (Jones et al.) focuses on how to trace a data flow from one end of a single autonomous system to another, given the signature and the egress point of the flow.
The previous solutions can be divided into two categories. The first one includes methods for tracking malicious continuous flows of IP packets and the second group includes the methods for tracking back single malicious IP packets. Some of the methods for tracking continuous flows may also be used to track-back single packets, such as for example the iTrace method referred to above. However, the price to pay is overwhelming.
Tracing-back single packets is still an unsolved problem, particularly if the tracking process contemplates minimizing the space requirement to store the intermediate data at each node. The hash-based solution identified above (Snoeren et al.) is in fact the only practical solution for tracking-back single malicious IP packets. Still, this solution is expensive for high-end core routers. For example, a router with 32 OC-192 links will need up to 30 Gbytes of memory to store one minute of traffic. On top of this, the time to update such a data structure will have to be added to the processing time of each single packet forwarded by a router.